﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ThreadTree
{
	class Program
	{
		static void Main(string[] args)
		{
			ThreadTreeManager manager=new ThreadTreeManager();
			//生成根节点
			ThreadTree<string> tree = CreateRoot();
			//生成节点
			AddNode(tree);
			ThreadTree<string> prevNode = null;
			//构建线索二叉树
			manager.BinTreeThreadingCreateLDR(ref tree,ref prevNode);
			Console.WriteLine("\n线索二叉树的遍历结果为：\n");
			//中序遍历线索二叉树
			manager.BinTreeThreadLDR(tree);
			Console.ReadLine();
		}

		#region 生成根节点
		
		/// <summary>
		/// 生成根节点
		/// </summary>
		/// <returns></returns>
		static ThreadTree<string> CreateRoot()
		{
			ThreadTree<string> tree=new ThreadTree<string>();
			Console.WriteLine("请输入根节点，方便我们生成树\n");
			tree.data = Console.ReadLine();
			Console.WriteLine("根节点已经生成\n");
			return tree;
		}

		#endregion

		#region 插入节点操作
		
		static ThreadTree<string> AddNode(ThreadTree<string> tree )
		{
			ThreadTreeManager manager=new ThreadTreeManager();
			while (true)
			{
				ThreadTree<string> node=new ThreadTree<string>();
				Console.WriteLine("请输入要插入节点的数据：\n");
				node.data = Console.ReadLine();
				Console.WriteLine("请输入要查找父节点的数据:\n");
				var parentData = Console.ReadLine();
				if (tree == null)
				{
					Console.WriteLine("未找到您输入的父节点，请重新输入。");
					continue;
				}
				Console.WriteLine("请确定要插入到父节点的:1 左侧，2 右侧");
				Direction direction = (Direction)Enum.Parse(typeof(Direction), Console.ReadLine());
				tree = manager.BinTreeThreadAddNode(tree, node, parentData, direction);
				Console.WriteLine("插入成功，是否继续？  1 继续， 2 退出");
				if (int.Parse(Console.ReadLine()) == 1)
					continue;
				else
					break;
			}
			return tree;
		}

		#endregion
	}

	#region 节点标识(用于判断孩子是节点还是线索)

	public enum NodeFlag
	{
		SubTree=1,
		Thread=2
	}

	#endregion

	#region 线索二叉树的结构

	public class ThreadTree<T>
	{
		public T data;
		public ThreadTree<T> left;
		public ThreadTree<T> right;
		public NodeFlag leftFlag;
		public NodeFlag rightFlag;
	}

	#endregion

	#region 插入左节点或者右节点

	public enum Direction
	{
		Left = 1,
		Right = 2
	}

	#endregion

	#region 线索二叉树的基本操作

	public class ThreadTreeManager
	{
		#region 将指定节点插入到二叉树中

		public ThreadTree<T> BinTreeThreadAddNode<T>(ThreadTree<T> tree,ThreadTree<T> node,T data,Direction direction)
		{
			if (tree == null)
				return null;
			if (tree.data.Equals(data))
			{
				switch (direction)
				{
					case Direction.Left:
						if (tree.left != null)
							throw new Exception("树的左节点不为空，不能插入");
						else
							tree.left = node;
						break;
					case Direction.Right:
						if (tree.right != null)
							throw new Exception("树的右节点不为空，不能插入");
						else
							tree.right = node;
						break;
				}
			}
			BinTreeThreadAddNode(tree.left, node, data, direction);
			BinTreeThreadAddNode(tree.right, node, data, direction);
			return tree;
		}

		#endregion

		#region 中序遍历构建线索二叉树

		public void BinTreeThreadingCreateLDR<T>(ref ThreadTree<T> tree,ref ThreadTree<T> prevNode )
		{
			if (tree==null)
			{
				return;
			}
			//先左子树遍历，寻找起始点
			BinTreeThreadingCreateLDR<T>(ref tree.left,ref prevNode);
			//如果left为空，则说明该节点可以放“线索”
			tree.leftFlag = (tree.left == null) ? NodeFlag.Thread : NodeFlag.SubTree;
			//如果right为空，则说明该节点可以放“线索”
			tree.rightFlag = (tree.right == null) ? NodeFlag.Thread : NodeFlag.SubTree;

			if(prevNode!=null)
			{
				if (tree.leftFlag == NodeFlag.Thread)
					tree.left = prevNode;
				if (prevNode.rightFlag == NodeFlag.Thread)
					prevNode.right = tree;
			}

			//保存前驱节点
			prevNode = tree;
			BinTreeThreadingCreateLDR(ref tree.right, ref prevNode);
		}


		#endregion

		#region 查找指定节点的后继

		public ThreadTree<T> BinTreeThreadNextLDR<T>(ThreadTree<T> tree)
		{
			if (tree == null)
				return null;
			//如果查找节点的标志域中是Thread，则直接获取
			if (tree.rightFlag == NodeFlag.Thread)
				return tree.right;
			else
			{
				//根据中序遍历的规则是寻找右子树中中序遍历的第一个节点
				var rightNode = tree.right;
                 //如果该节点是subTree就需要循环遍历
                 while (rightNode.leftFlag == NodeFlag.SubTree)
                 {
                     rightNode = rightNode.left;
                 }
                 return rightNode;
			}
		}

		#endregion

		#region 查找指定节点的前驱

		public ThreadTree<T> BinTreeThreadPrevLDR<T>(ThreadTree<T> tree)
		{
			if (tree == null)
				return null;
			//如果查找节点的标志域中是线索，那么可以直接找出来
			if (tree.rightFlag == NodeFlag.Thread)
				return tree.right;
			else
			{
				//根据中序遍历的规则如果不为Thread，则要找出左子树的最后节点,也就是左子树中最后输出的元素
				var leftNode = tree.left;
				//如果该节点是subTree就需要循环遍历
				while (leftNode.leftFlag == NodeFlag.SubTree)
				{
					leftNode = leftNode.right;
				}
				return leftNode;
			}
		}

		#endregion

		#region 遍历线索二叉树
        
        public void BinTreeThreadLDR<T>(ThreadTree<T> tree)
        {
            if (tree == null)
                return; 
            while (tree.leftFlag == NodeFlag.SubTree)
                tree = tree.left;
            do
            {
                Console.Write(tree.data + "\t");
                tree = BinTreeThreadNextLDR(tree);
            } while (tree != null);
        }

         #endregion
	}


	#endregion
}
